primal spars max margin markov network jun zhu eric xing bo zhang max margin markov network shown great promis structur predict relat learn due kkt condit enjoi dual sparsiti exist formul enjoi primal sparsiti desir properti select signific featur reduc risk fit paper present norm regular max margin markov network enjoi dual primal sparsiti simultan learn present method includ project gradient cut plane em style algorithm base equival adapt perform extens empir studi synthet real data set experiment result show effect select signific featur perform pseudo primal spars laplac predict accuraci consist outperform compet method enjoi primal dual sparsiti em algorithm robust pre diction accuraci time effici 